package com.pfsoft.leetcode;

import java.util.regex.Pattern;

/**
 * @author pengfei
 * @date 2022年07月28日 11:13
 * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
 * <p>
 * 如果可以，返回 true ；否则返回 false 。
 * <p>
 * magazine 中的每个字符只能在 ransomNote 中使用一次。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：ransomNote = "a", magazine = "b"
 * 输出：false
 * 示例 2：
 * <p>
 * 输入：ransomNote = "aa", magazine = "ab"
 * 输出：false
 * 示例 3：
 * <p>
 * 输入：ransomNote = "aa", magazine = "aab"
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= ransomNote.length, magazine.length <= 105
 * ransomNote 和 magazine 由小写英文字母组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ransom-note
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question383 {

    public static void main(String[] args){
        Question383 question383=new Question383();
//        System.out.println(question383.canConstruct("fihjjjjei", "hjibagacbhadfaefdjaeaebgi"));

        System.out.println(question383.canConstruct2("fihjjjjei", "hjibagacbhadfaefdjaeaebgi"));
    }

    /**
     * 自己盲写的答案。。。。虽然傻逼，但是也算解出来了，记录之
     * * 1 <= ransomNote.length, magazine.length <= 105
     * * ransomNote 和 magazine 由小写英文字母组成
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        boolean result = true;
        if (ransomNote.length() < 1 || ransomNote.length() > 105) {
            System.out.println("超长");
        }
        if (!(this.checkRule(ransomNote) || this.checkRule(magazine))) {
            System.out.println("only lowly character");
        }
        if (magazine.length() < ransomNote.length()) {
            result = false;
        } else {
            char[] ransomNoteChars = ransomNote.toCharArray();
            char[] magazineChars = magazine.toCharArray();
            CharSign[] charSigns=new CharSign[magazineChars.length];
            CharSign charSign;
            for(int i=0;i<magazineChars.length;i++){
                charSign=new CharSign(magazineChars[i],false);
                charSigns[i]=charSign;
            }
            for (int i = 0; i < ransomNoteChars.length; i++) {
                boolean found=false;
                for(int j=0;j<charSigns.length;j++){
                    if(ransomNoteChars[i]== charSigns[j].c && !charSigns[j].used){
                        charSigns[j].used=true;
                        found=true;
                        break;
                    }
                }
                if(!found){ //任何一个字母没找到，或者没找到足够可用的都直接返回false
                    return false;
                }
            }
        }
        return result;
    }

    public  class  CharSign{
        private char c;
        private boolean used=false;

        public CharSign(char c, boolean used) {
            this.c = c;
            this.used = used;
        }

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public boolean isUsed() {
            return used;
        }

        public void setUsed(boolean used) {
            this.used = used;
        }
    }

    private boolean checkRule(String inputString) {
        return Pattern.matches("[a-z]", inputString);
    }


    /**
     * 优秀答案
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct1(String ransomNote, String magazine) {
        //这一个跟我一样
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        //这个26是个什么鬼？是因为26个字母么？ 看了后面的发现还真是。
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            //这个看不懂呀。。。 懂了，。。。把26个字母拿来计数，最后去遍历ransomNote每个字母数量够不够，不够肯定就有问题，我之前也想到这种方式了，但是是加了个内部类，增加个标记属性的方式。突然感觉效率差但是我的易理解啊，haha
            //不过他这个写法也确实学到了。以小写字母a作为基准线，。后面其他字母的assic码值与他的差值，就是之前定义的cnt（26个小写字母数组的下标），然后存在一次就计数一次，相当于记录了每个字母出现的次数，方便后面与ransomNote中字母的计数去对比
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }


    /**
     * 看懂别人写的以后，自己盲写的
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct2(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] charArray=new int[26];
        for(char c:magazine.toCharArray()){
            //数组初始都是填充的0，这里仿照别人写的++的方式计数
            charArray[c-'a']++;
        }
        for(char c: ransomNote.toCharArray()){
            //每用一个就减一次技术，不足就return false
            charArray[c-'a']--;
            if(charArray[c-'a']<0){
                return false;
            }
        }
        return true;
    }



}
